package com.stephen.data.hashtab;

import java.util.Scanner;

/**
 * @author: stephen
 * @create: 2020-02-01 13:22
 * @description: 哈希表的实现
 */
public class HashTabDemo {

    public static void main(String[] args) {

        HashTab hashTab = new HashTab(7);
        String key = "";
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("add: 添加员工");
            System.out.println("find: 查找员工");
            System.out.println("del: 删除员工");
            System.out.println("list: 遍历员工");
            System.out.println("exit: 退出系统");
            key = scanner.next();
            switch (key) {
                case "add":
                    System.out.println("请输入id");
                    int id = scanner.nextInt();
                    System.out.println("请输入name");
                    String name = scanner.next();
                    Emp emp = new Emp(id, name);
                    hashTab.add(emp);
                    break;
                case "list":
                    hashTab.list();
                    break;
                case "find":
                    System.out.println("请输入id");
                    id = scanner.nextInt();
                    hashTab.findById(id);
                    break;
                case "del":
                    System.out.println("请输入id");
                    id = scanner.nextInt();
                    hashTab.del(id);
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
                    break;
                default:
                    break;
            }
        }
    }

}

// 创建HashTab,管理多条链表
class HashTab {
    // 数组中每个元素,都表示一个链表
    private EmpLinkedList[] empLinkedListArray;

    private int size;

    public HashTab(int size) {
        this.size = size;
        // 初始化数组
        empLinkedListArray = new EmpLinkedList[size];
        // 这个地方需要初始化每个链表,否则会有空指针
        // 此时虽然创建了数组,但是数组中每个元素都是null,无法添加员工
        for (int i = 0; i < size; i++) {
            empLinkedListArray[i] = new EmpLinkedList();
        }
    }

    /**
     * 删除元素
     * @param id
     */
    public void del(int id) {
        int index = hashModel(id);
        empLinkedListArray[index].del(id);
    }

    /**
     * 根据id查找
     * @param id 员工的id
     * @return
     */
    public void findById(int id) {
        int index = hashModel(id);
        Emp emp = empLinkedListArray[index].findById(id);
        if (null == emp) {
            System.out.printf("未找到员工信息,id为%d\n",id);
        } else {
            System.out.printf("在第[%d]条链表中,找到员工 id=%d \n",index + 1,id);
        }
    }

    /**
     * 遍历所有链表
     */
    public void list() {
        for (int i = 0; i < size; i++) {
            empLinkedListArray[i].list(i);
        }
    }

    /**
     * 添加
     * @param emp
     */
    public void add(Emp emp) {
        // 根据员工id,决定添加到哪个链表
        int index = hashModel(emp.id);
        // 将emp添加到对应链表中
        empLinkedListArray[index].add(emp);

    }

    /**
     * 散列函数,取模
     * @param id
     * @return
     */
    public int hashModel(int id) {
        return id % size;
    }

}


// 员工信息
class Emp {
    public int id;
    public String name;
    public Emp next;

    public Emp(int id, String name) {
        this.id = id;
        this.name = name;
    }
}

// EmpLinkedList,表示链表
class EmpLinkedList {
    // 链表的头指针,是指向第一个Emp
    private Emp head; // 默认null

    /**
     * 根据id来删除员工
     * @param id
     */
    public void del(int id) {
        // 遍历链表
        if (head == null) {
            System.out.println("链表为空,无法删除");
            return;
        }
        // 找到要删除的元素的上一个元素
        boolean ifFind = false;
        Emp curEmp = head; // 此时head就是链表的第一个元素
        while (true) {
            if (head.id == id) {
                // 说明第一个就是要找的元素
                ifFind = true;
                break;
            } else if (curEmp.next != null && curEmp.next.id == id) {
                ifFind = true;
                break;
            }
            // 如果第一个不是,才看后边的元素
            if (curEmp.next == null) {
                break;
            }

            // 向后移一位
            curEmp = curEmp.next;
        }
        // 把上一个元素指向很删除的元素的下一个
        if (ifFind) {
            if (head.id == id) { // 如果要删除的元素是链表的第一个,要特殊处理
                head = curEmp.next;
            } else if (curEmp.next != null && curEmp.next.id == id) { // 如果是最后一个元素,也要特殊处理
                curEmp.next = null; // 前一个元素指向空即可
            } else { // 其它的,都是找的前一个元素,可以直接指向下下个元素即可
                curEmp.next = curEmp.next.next;
            }
            System.out.printf("删除id为 %d 的元素成功\n",id);
        } else {
            System.out.printf("没有找到id为 %d 的元素\n",id);
        }
    }

    /**
     * 根据id来查找员工
     * @param id
     * @return
     */
    public Emp findById(int id) {
        if (head == null) {
            System.out.println("链表为空");
            return null;
        }
        Emp cur = head;
        while (true) {
            if (cur.id == id) { // 说明找到了
                break;
            }
            if (cur.next == null) { // 没有找到
                cur = null;
                break;
            }

            cur = cur.next;
        }

        return cur;
    }

    /**
     * 链表中添加元素
     * 全部添加到链表最后
     * @param emp 添加的员工
     */
    public void add(Emp emp) {
        // 添加第一个员工
        if (head == null) {
            head = emp;
            return;
        }
        // 如果不是第一个员工,就使用一个辅助指针,定位到链表的最后
        Emp curEmp = head;
        while (true) {
            if (curEmp.next == null) { // 此时已经到链表最后
                break;
            }
            // 后移
            curEmp = curEmp.next;
        }
        // 退出时添加到链表的最后
        curEmp.next = emp;
    }

    /**
     * 遍历链表
     */
    public void list(int index) {
        if (head == null) {// 说明链表为空
            System.out.printf("第 %d 个链表为空\n",index + 1);
            return;
        }
        System.out.printf("第 %d 个链表的信息为 => ",index + 1);
        Emp curEmp = head; // 辅助指针
        while (true) {
            System.out.printf("id = %d name = %s,",curEmp.id,curEmp.name);
            if (curEmp.next == null) {
                break;
            }
            curEmp = curEmp.next;
        }
        System.out.println();
    }

}